ICPC Live Archive/4788 - Castles/4788.cpp

   1 #include <algorithm>
   2 #include <iostream>
   3 #include <iterator>
   4 #include <sstream>
   5 #include <fstream>
   6 #include <cassert>
   7 #include <climits>
   8 #include <cstdlib>
   9 #include <cstring>
  10 #include <string>
  11 #include <cstdio>
  12 #include <vector>
  13 #include <cmath>
  14 #include <queue>
  15 #include <deque>
  16 #include <stack>
  17 #include <list>
  18 #include <map>
  19 #include <set>
  20
  21 using namespace std;
  22
  23 template <class T> string toStr(const T &x){
  24 stringstream s; s << x; return s.str();
  25 }
  26
  27 template <class T> int toInt(const T &x){
  28 stringstream s; s << x; int r; s >> r; return r;
  29 }
  30
  31 #define For(i, a, b) for (int i=(a); i<(b); ++i)
  32 #define foreach(x, v) for (typeof (v).begin() x = (v).begin(); x != (v).end(); ++x)
  33 #define D(x) cout << #x " = " << (x) << endl
  34
  35 const double EPS = 1e-9;
  36 int cmp(double x, double y, double tol = EPS){
  37   return (x <= y + tol) ? (x + tol < y) ? -1 : 0 : 1;
  38 }
  39
  40 const int MAXN = 105;
  41
  42 int A[MAXN], B[MAXN];
  43
  44 vector<int> g[MAXN];
  45
  46 bool segundo_de_mayor_a_menor(pair<int, int> a, pair<int, int> b){
  47   if (a.second != b.second) return a.second > b.second;
  48   return a.first < b.first;
  49 }
  50
  51
  52 pair<int, int> f(int u, int dad = -1){
  53   vector< pair<int, int> > p;
  54   for (int i = 0; i < g[u].size(); ++i){
  55     int v = g[u][i];
  56     if (v == dad) continue;
  57
  58     p.push_back( f(v, u) );
  59   }
  60
  61   sort(p.begin(), p.end(), segundo_de_mayor_a_menor);
  62
  63   int total = A[u];
  64   int tengo = A[u] - B[u];
  65   for (int i = 0; i < p.size(); ++i){
  66     if (tengo > p[i].first){
  67       tengo -= p[i].first - p[i].second;
  68     }else{
  69       total += p[i].first - tengo;
  70       tengo = p[i].second;
  71     }
  72   }
  73   //printf(" f(u=%d) = <%d, %d>\n", u, total, tengo);
  74   return make_pair(total, tengo);
  75 }
  76
  77 int main(){
  78   int n, Caso = 1;
  79   while (cin >> n){
  80     if (n == 0) break;
  81     cout << "Case " << Caso++ << ": ";
  82
  83     for (int i = 0; i < n; ++i){
  84       int x, y, z;
  85       cin >> x >> y >> z;
  86       A[i] = x;
  87       B[i] = y + z;
  88       A[i] = max(A[i], B[i]);
  89
  90       g[i].clear();
  91     }
  92
  93     for (int i = 0; i < n - 1; ++i){
  94       int u, v;
  95       cin >> u >> v;
  96       u--, v--;
  97       g[u].push_back(v);
  98       g[v].push_back(u);
  99     }
 100
 101     //for (int i = 0; i < n; ++i){
 102     //  printf("Nodo %d: A = %d, B = %d\n", i, A[i], B[i]);
 103     //}
 104
 105     int ans = INT_MAX;
 106     for (int i = 0; i < n; ++i){
 107
 108       pair<int, int> p = f(i);
 109       //printf("Empezando en %d: <%d, %d>\n", i, p.first, p.second);
 110
 111
 112       ans = min(ans, p.first);
 113
 114     }
 115
 116     cout << ans << endl;
 117   }
 118   return 0;
 119 }